package com.justnow.offer;

public class Solution14_1 {

    /**
     * 方法一：递归，递归函数为F(n) = max(i*(n-i), i*F(n-i))
     * 每次将绳子分为两端，长度分别为i和n-i，现在需要判断的是i*(n-i)和i*F(n-i)的大小。这里的
     * F(n)的含义是：长度为n，切割成m段儿的最大乘积
     *
     * @param n
     * @return
     */
    public static int cuttingRope1(int n) {
        if (n == 2)
            return 1;
        int res = -1;
        for (int i = 1; i < n; i++) {
            //将绳子分为两段的方法共有n-1中方法，那么就需要判断者n-1次中的最大值
            res = Math.max(res, Math.max(i * cuttingRope1(n - i), i * (n - i)));
        }
        return res;
    }

    /**
     * 方法二，记忆化搜索, 自顶项向下
     * @param n
     * @return
     */
    private int[] memory;
    public int cuttingRope2(int n) {
        memory = new int[n+1];
        return cuttingRopeHelper(n);
    }

    public int cuttingRopeHelper(int n) {
        if (n == 2) return 1;
        if (memory[n] != 0) return memory[n]; //memory的初始化子为0，如果它不为0，说明已经计算过了，直接返回即可
        int res = -1;
        for (int i = 1; i < n - 1; i++) {
            res = Math.max(res, Math.max(i * (n - i), i * cuttingRopeHelper(n - i)));
        }
        //将每次计算的结果保存到备忘录数组中
        memory[n] = res;
        return res;
    }

    /**
     * 方法三，动态规划
     * @param n
     * @return
     */
    public int cuttingRope3(int n) {
        int[] dp = new int[n + 1]; //dp[i]，表示长度的i的绳子的最大乘积
        dp[2] = 1;
        for (int i = 3; i < n + 1; i++) { //切一刀将绳子分成两部分，i和n-i

            for (int j = 0; j < i; j++) { //对长度为i的这一部分，继续切割，分为j和i-j

                dp[i] = Math.max(dp[i], Math.max((i - j) * j, j * dp[i - j])); //状态转移方程为，dp[i]与长度为i的部分进行分切的乘积大小
                // 长度为i又可以分为两种情况，
                // 情况一，分为j和i-j之后，不再进行分切
                // 情况二，分为j和i-j之后，再对i-j进行分切
            }
        }

        return dp[n];
    }
    public static void main(String[] args) {
        int s1 = Solution14_1.cuttingRope1(10);
        System.out.println(s1);
    }
}
